To solve the problem of uncertain Quality of Service (QoS)-aware cloud service composition optimization, an Uncertain-Long Time Series (ULST) model and Tournament strategy based Genetic Algorithm (T-GA) was proposed. Firstly, based on different access rules of users to services in different periods, the long-term change of QoS was modeled as an uncertain-long time series, which can accurately describe the users' actual QoS access record to service over a period of time. Secondly, an improved genetic algorithm based on uncertain QoS model was proposed, which used tournament strategy instead of basic roulette wheel selection strategy. Finally, a lot of experiments were carried out on real data. The uncertain-long time series model can effectively solve the problem of uncertain QoS-aware cloud service composition; the proposed T-GA is superior to the Genetic Algorithm based on Elite selection strategy (E-GA) in optimization results and stability, and the execution speed is improved by almost one time, which is a feasible, high efficient and stable algorithm.